﻿// 4620. 旅行.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/4623/


给定一个 n
 个节点的树，节点编号为 1∼n
。

请你从中选择一个简单路径（不能包含重复节点或重复的边），并沿所选路径来一场旅行，更具体的说，就是从所选路径的一个端点沿路径前往另一个端点。

注意，所选简单路径可以只由一个节点组成。

旅行需要花费能量。

初始时，你的能量为 0
。

在旅行过程中：

每经过一个节点（包括起点和终点），就可以得到该节点的能量，其中节点 i
 包含的能量为 wi
。
每经过一条边 (u,v)
，就需要消耗一定的能量 c
。
你设计的旅行路线应满足：

在经过任何一条边之前，你的现有能量都不能少于该边所需消耗的能量（否则，将无法顺利通过该边）。
在满足条件 1
 的前提下，旅行结束时，剩余的能量尽可能大。
请计算并输出剩余能量的最大可能值。

输入格式
第一行包含整数 n
。

第二行包含 n
 个整数 w1,w2,…,wn
。

接下来 n−1
 行，每行包含三个整数 u,v,c
，表示存在一条边 (u,v)
，经过它所需的能量为 c
。

保证给定图是一棵树。

输出格式
一个整数，表示剩余能量的最大可能值。

数据范围
前 3
 个测试点满足 1≤n≤5
。
所有测试点满足 1≤n≤3×105
，0≤wi≤109
，1≤u,v≤n
，u≠v
，1≤c≤109
。

输入样例1：
3
1 3 3
1 2 2
1 3 2
输出样例1：
3
输入样例2：
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
输出样例2：
7

*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 